package leetcode._350;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class Solution {

	
	public int[] intersection(int[] nums1, int[] nums2) {
		TreeMap<Integer, Integer> map = new TreeMap<>();
		for (int n : nums1) {
			if (!map.containsKey(n)) {
				map.put(n, 1);
			} else {
				map.put(n, map.get(n) + 1);
			}
		}
		
		List<Integer> list = new ArrayList<>();
		for (int n : nums2) {
			if (map.containsKey(n)) {
				list.add(n);
				map.put(n, map.get(n) - 1);
				if (map.get(n) == 0) {
					map.remove(n);
				}
			}
		}
		int[] res = new int[list.size()];
		for (int i = 0; i < list.size(); i++) {
			res[i] = list.get(i);
		}
		return res;
    }
}
